#include<iostream>
using namespace std;
long long num[2050]={0};
long long dp[3][2020][2020]={0};
int lst[2020]={0};
int pla[2020]={0};
long long ans[4][2020]={0};
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int ttt;
    cin>>ttt;
    for(int sss=0;sss<ttt;sss++){
        for(int i=0;i<3;i++){
            for(int j=0;j<2002;j++){
                ans[i][j]=-999999999;
            }
        }
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>num[i];
        }
        for(int i=0;i<2;i++){
            for(int j=0;j<2002;j++){
                    for(int k=0;k<2002;k++)
                dp[i][j][k]=0;
            }
        }
        for(int i=0;i<2002;i++)pla[i]=-1;
        for(int i=0;i<n;i++){
            if(pla[num[i]]==-1){
                pla[num[i]]=i;
                lst[i]=-1;
            }
            else{
                lst[i]=pla[num[i]];
                pla[num[i]]=i;
            }
        }
        for(int i=0;i<10;i++){
           // cout<<lst[i]<<" ";
        }
        //cout<<endl;
        dp[0][0][1]=0;
        ans[0][0]=0;
        for(int i=1;i<n;i++){
            for(int j=1;j<=i+1;j++){
                ans[0][i-1]=max(ans[0][i-1],dp[0][i-1][j]);
                ans[1][i-1]=max(ans[1][i-1],dp[1][i-1][j]);
            }
            if(num[i]==num[i-1]){
                for(int j=1;j<=i+1;j++){
                    dp[0][i][j]=dp[0][i-1][j-1]+num[i];
                    dp[1][i][j]=dp[1][i-1][j-1]+num[i];
                }
                continue;
            }
            for(int j=2;j<=i+1;j++){
                dp[0][i][j]=dp[0][i-1][j-1];
                dp[1][i][j]=dp[1][i-1][j-1];
            }
            dp[0][i][1]=ans[1][i-1];
            dp[1][i][1]=ans[0][i-1];
            if(lst[i]==-1){
                continue;
            }
            dp[0][i][1]=max(dp[1][i-1][i-lst[i]-1]+num[i],ans[1][i-1]);
            dp[1][i][1]=max(dp[0][i-1][i-lst[i]-1]+num[i],ans[0][i-1]);
            //if(i==5)cout<<dp[1][i-1][i-lst[num[i]]-1]+num[i]<<" "<<i-lst[num[i]]-1<<endl;
        }
        for(int j=1;j<=n;j++){
            ans[0][n-1]=max(ans[0][n-1],dp[0][n-1][j]);
            ans[1][n-1]=max(ans[1][n-1],dp[1][n-1][j]);
        }
        cout<<max(ans[0][n-1],ans[1][n-1])<<endl;
    }
    return 0;
    }
